home *** CD-ROM | disk | FTP | other *** search
/ Qoole for Quake / Qoole for Quake (USA) / Qoole for Quake (USA).bin / Tutorial / HTML / QUBE.ZIP / SRC / SURFACES.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-11-05  |  11.5 KB  |  605 lines
  1. /* divide.h */
  2.  
  3. #include "bsp5.h"
  4.  
  5.  
  6. surface_t    newcopy_t;
  7.  
  8. int        FaceEdgesTotal;
  9. int        FaceEdgeCur;
  10.  
  11. /*
  12. a surface has all of the faces that could be drawn on a given plane
  13.  
  14. the outside filling stage can remove some of them so a better bsp can be generated
  15.  
  16. */
  17.  
  18. int    subdivides;
  19.  
  20. #if 0
  21. /*
  22. ===============
  23. SubdivideFace
  24.  
  25. If the face is >256 in either texture direction, carve a valid sized
  26. piece off and insert the remainder in the next link
  27. ===============
  28. */
  29. void SubdivideFace (face_t *f, face_t **prevptr)
  30. {
  31.     vec3_t        mins, maxs;
  32.     double        v;
  33.     int            i,j;
  34.     plane_t        plane;
  35.     face_t        *front, *back, *next;
  36.     float        size[3];
  37.     
  38. /* special (non-surface cached) faces don't need subdivision */
  39.     if ( texinfo[f->texturenum].flags & TEX_SPECIAL)
  40.         return;
  41.  
  42.     do
  43.     {
  44.         mins[0] = mins[1] = mins[2] = 9999;
  45.         maxs[0] = maxs[1] = maxs[2] = -9999;
  46.         
  47.         for (i=0 ; i<f->numpoints ; i++)
  48.             for (j=0 ; j<3 ; j++)
  49.             {
  50.                 v = f->pts[i][j];
  51.                 if (v < mins[j])
  52.                     mins[j] = v;
  53.                 if (v > maxs[j])
  54.                     maxs[j] = v;
  55.             }
  56.             
  57.         for (i=0 ; i<3 ; i++)
  58.             size[i] = maxs[i] - mins[i];
  59.             
  60. #if 0
  61. if ( !size[0] && size[1] <= 496 && size[2] <= 496 && size[1]*size[2]<0x10000)
  62.     return;
  63. if ( !size[1] && size[0] <= 496 && size[2] <= 496 && size[0]*size[2]<0x10000)
  64.     return;
  65. if ( !size[2] && size[0] <= 496 && size[1] <= 496 && size[0]*size[1]<0x10000)
  66.     return;
  67. #endif
  68.  
  69.         for (i=0 ; i<3 ; i++)
  70.         {
  71.             v = maxs[i] - mins[i];
  72.             if (v <= 240)    /* NOT 256, because of 16 pixel edge crossings */
  73.                 continue;
  74.                 
  75.         /* split it */
  76.             subdivides++;
  77.             
  78.             plane.normal[0] = plane.normal[1] = plane.normal[2] = 0;
  79.             plane.normal[i] = 1;
  80.             plane.dist = maxs[i] - 224;    /* not 240, because of epsilons */
  81.             next = f->next;
  82.             SplitFace (f, &plane, &front, &back);
  83.             if (!front || !back)
  84.                 Error ("SubdivideFace: didn't split the polygon");
  85.             *prevptr = front;
  86.             front->next = back;
  87.             back->next = next;
  88.             f = front;
  89.             break;
  90.         }
  91.         
  92.     } while (i < 3);
  93. }
  94. #endif
  95.  
  96. #if 1
  97.  
  98. /*
  99. ===============
  100. SubdivideFace
  101.  
  102. If the face is >256 in either texture direction, carve a valid sized
  103. piece off and insert the remainder in the next link
  104. ===============
  105. */
  106. void SubdivideFace (face_t *f, face_t **prevptr)
  107. {
  108.     float        mins, maxs;
  109.     double        v;
  110.     int            axis, i;
  111.     plane_t        plane;
  112.     face_t        *front, *back, *next;
  113.     texinfo_t    *tex;
  114.  
  115. /* special (non-surface cached) faces don't need subdivision */
  116.     tex = &texinfo[f->texturenum];
  117.  
  118.     if ( tex->flags & TEX_SPECIAL)
  119.         return;
  120.  
  121.  
  122.     for (axis = 0 ; axis < 2 ; axis++)
  123.     {
  124.         while (1)
  125.         {
  126.             mins = 9999;
  127.             maxs = -9999;
  128.             
  129.             for (i=0 ; i<f->numpoints ; i++)
  130.             {
  131.                 v = DotProduct (f->pts[i], tex->vecs[axis]);
  132.                 if (v < mins)
  133.                     mins = v;
  134.                 if (v > maxs)
  135.                     maxs = v;
  136.             }
  137.         
  138.             if (maxs - mins <= 240)
  139.                 break;
  140.             
  141.         /* split it */
  142.             subdivides++;
  143.             
  144.             VectorCopy (tex->vecs[axis], plane.normal);
  145.             v = VectorLength (plane.normal);
  146.             VectorNormalize (plane.normal);            
  147.             plane.dist = (mins + 224)/v;
  148.             next = f->next;
  149.             SplitFace (f, &plane, &front, &back);
  150.             if (!front || !back)
  151.                 Error ("SubdivideFace: didn't split the polygon");
  152.             *prevptr = back;
  153.             back->next = front;
  154.             front->next = next;
  155.             f = back;
  156.         }
  157.     }
  158. }
  159. #endif
  160.  
  161.  
  162. /*
  163. ================
  164. SubdivideFaces
  165. ================
  166. */
  167. void SubdivideFaces (surface_t *surfhead)
  168. {
  169.     surface_t       *surf;
  170.     face_t          *f , **prevptr;
  171.  
  172.     ShowStatusEntry("Subdividing faces.");
  173.  
  174.     subdivides = 0;
  175.  
  176.     for (surf = surfhead ; surf ; surf=surf->next)
  177.     {
  178.         prevptr = &surf->faces;
  179.         while (1)
  180.         {
  181.             f = *prevptr;
  182.             if (!f)
  183.                 break;
  184.             SubdivideFace (f, prevptr);
  185.             f = *prevptr;
  186.             prevptr = &f->next;
  187.         }
  188.     }
  189.  
  190.     ShowTempEntry("%i faces added by subdivision", subdivides);
  191. }
  192.  
  193.  
  194. /*
  195. =============================================================================
  196.  
  197. GatherNodeFaces
  198.  
  199. Frees the current node tree and returns a new chain of the surfaces that
  200. have inside faces.
  201. =============================================================================
  202. */
  203.  
  204. void GatherNodeFaces_r (node_t *node)
  205. {
  206.     face_t    *f, *next;
  207.     
  208.     if (node->planenum != PLANENUM_LEAF)
  209.     {
  210. /* */
  211. /* decision node */
  212. /* */
  213.         for (f=node->faces ; f ; f=next)
  214.         {
  215.             next = f->next;
  216.             if (!f->numpoints)
  217.             {    /* face was removed outside */
  218.                 FreeFace (f);
  219.             }
  220.             else
  221.             {
  222.                 f->next = validfaces[f->planenum];
  223.                 validfaces[f->planenum] = f;
  224.             }
  225.         }
  226.         
  227.         GatherNodeFaces_r (node->children[0]);
  228.         GatherNodeFaces_r (node->children[1]);
  229.         
  230.         free (node);
  231.     }
  232.     else
  233.     {
  234. /* */
  235. /* leaf node */
  236. /* */
  237.         free (node);
  238.     }
  239. }
  240.  
  241. /*
  242. ================
  243. GatherNodeFaces
  244.  
  245. ================
  246. */
  247. surface_t *GatherNodeFaces (node_t *headnode)
  248. {
  249.     memset (validfaces, 0, sizeof(validfaces));
  250.     GatherNodeFaces_r (headnode);
  251.     return BuildSurfaces ();    
  252. }
  253.  
  254. /*=========================================================================== */
  255.  
  256. typedef struct hashvert_s
  257. {
  258.     struct hashvert_s    *next;
  259.     vec3_t    point;
  260.     int        num;
  261.     int        numplanes;        /* for corner determination */
  262.     int        planenums[2];
  263.     int        numedges;
  264. } hashvert_t;
  265.  
  266. #define    POINT_EPSILON    0.01
  267.  
  268. int        c_cornerverts;
  269.  
  270. hashvert_t    hvertex[MAX_MAP_VERTS];
  271. hashvert_t    *hvert_p;
  272.  
  273. face_t        *edgefaces[MAX_MAP_EDGES][2];
  274. int        firstmodeledge = 1;
  275. int        firstmodelface;
  276.  
  277. /*============================================================================ */
  278.  
  279. #define    NUM_HASH    4096
  280.  
  281. hashvert_t    *hashverts[NUM_HASH];
  282.  
  283. static    vec3_t    hash_min, hash_scale;
  284.  
  285. static    void InitHash (void)
  286. {
  287.     vec3_t    size;
  288.     double    volume;
  289.     double    scale;
  290.     int        newsize[2];
  291.     int        i;
  292.     
  293.     memset (hashverts, 0, sizeof(hashverts));
  294.  
  295.     for (i=0 ; i<3 ; i++)
  296.     {
  297.         hash_min[i] = -8000;
  298.         size[i] = 16000;
  299.     }
  300.  
  301.     volume = size[0]*size[1];
  302.     
  303.     scale = sqrt(volume / NUM_HASH);
  304.  
  305.     newsize[0] = size[0] / scale;
  306.     newsize[1] = size[1] / scale;
  307.  
  308.     hash_scale[0] = newsize[0] / size[0];
  309.     hash_scale[1] = newsize[1] / size[1];
  310.     hash_scale[2] = newsize[1];
  311.     
  312.     hvert_p = hvertex;
  313. }
  314.  
  315. static    unsigned HashVec (vec3_t vec)
  316. {
  317.     unsigned    h;
  318.     
  319.     h =    hash_scale[0] * (vec[0] - hash_min[0]) * hash_scale[2]
  320.         + hash_scale[1] * (vec[1] - hash_min[1]);
  321.     if ( h >= NUM_HASH)
  322.         return NUM_HASH - 1;
  323.     return h;
  324. }
  325.  
  326.  
  327. /*
  328. =============
  329. GetVertex
  330. =============
  331. */
  332. int    GetVertex (vec3_t in, int planenum)
  333. {
  334.     int            h;
  335.     int            i;
  336.     hashvert_t    *hv;
  337.     vec3_t        vert;
  338.     
  339.     for (i=0 ; i<3 ; i++)
  340.     {
  341.         if ( fabs(in[i] - Q_rint(in[i])) < 0.001)
  342.             vert[i] = Q_rint(in[i]);
  343.         else
  344.             vert[i] = in[i];
  345.     }
  346.     
  347.     h = HashVec (vert);
  348.     
  349.     for (hv=hashverts[h] ; hv ; hv=hv->next)
  350.     {
  351.         if ( fabs(hv->point[0]-vert[0])<POINT_EPSILON
  352.         && fabs(hv->point[1]-vert[1])<POINT_EPSILON
  353.         && fabs(hv->point[2]-vert[2])<POINT_EPSILON )
  354.         {
  355.             hv->numedges++;
  356.             if (hv->numplanes == 3)
  357.                 return hv->num;        /* allready known to be a corner */
  358.             for (i=0 ; i<hv->numplanes ; i++)
  359.                 if (hv->planenums[i] == planenum)
  360.                     return hv->num;        /* allready know this plane */
  361.             if (hv->numplanes == 2)
  362.                 c_cornerverts++;
  363.             else
  364.                 hv->planenums[hv->numplanes] = planenum;
  365.             hv->numplanes++;
  366.             return hv->num;
  367.         }
  368.     }
  369.     
  370.     hv = hvert_p;
  371.     hv->numedges = 1;
  372.     hv->numplanes = 1;
  373.     hv->planenums[0] = planenum;
  374.     hv->next = hashverts[h];
  375.     hashverts[h] = hv;
  376.     VectorCopy (vert, hv->point);
  377.     hv->num = numvertexes;
  378.     if (hv->num==MAX_MAP_VERTS)
  379.         Error ("GetVertex: MAX_MAP_VERTS");
  380.     hvert_p++;
  381.         
  382. /* emit a vertex */
  383.     if (numvertexes == MAX_MAP_VERTS)
  384.         Error ("numvertexes == MAX_MAP_VERTS");
  385.  
  386.     dvertexes[numvertexes].point[0] = vert[0];
  387.     dvertexes[numvertexes].point[1] = vert[1];
  388.     dvertexes[numvertexes].point[2] = vert[2];
  389.     numvertexes++;
  390.  
  391.     return hv->num;
  392. }
  393.  
  394. /*=========================================================================== */
  395.  
  396.  
  397. /*
  398. ==================
  399. GetEdge
  400.  
  401. Don't allow four way edges
  402. ==================
  403. */
  404. int    c_tryedges;
  405.  
  406. int GetEdge (vec3_t p1, vec3_t p2, face_t *f)
  407. {
  408.     int        v1, v2;
  409.     dedge_t    *edge;
  410.     int        i;
  411.  
  412.     if (!f->contents[0])
  413.         Error ("GetEdge: 0 contents");
  414.  
  415.     c_tryedges++;        
  416.     v1 = GetVertex (p1, f->planenum);
  417.     v2 = GetVertex (p2, f->planenum);
  418.     for (i=firstmodeledge ; i < numedges ; i++)
  419.     {
  420.         edge = &dedges[i];
  421.         if (v1 == edge->v[1] && v2 == edge->v[0]
  422.         && !edgefaces[i][1]
  423.         && edgefaces[i][0]->contents[0] == f->contents[0])
  424.         {
  425.             edgefaces[i][1] = f;
  426.             return -i;
  427.         }
  428.     }
  429.     
  430. /* emit an edge */
  431.     if (numedges == MAX_MAP_EDGES)
  432.         Error ("numedges == MAX_MAP_EDGES");
  433.     edge = &dedges[numedges];
  434.     numedges++;
  435.     edge->v[0] = v1;
  436.     edge->v[1] = v2;
  437.     edgefaces[i][0] = f;
  438.     
  439.     return i;
  440. }
  441.  
  442.  
  443. /*
  444. ==================
  445. FindFaceEdges
  446. ==================
  447. */
  448. void FindFaceEdges (face_t *face)
  449. {
  450.     int        i;
  451.  
  452.     face->outputnumber = -1;    
  453.     if (face->numpoints > MAXEDGES)
  454.         Error ("WriteFace: %i points", face->numpoints);
  455.  
  456.     for (i=0; i<face->numpoints ; i++)
  457.         face->edges[i] =  GetEdge
  458.         (face->pts[i], face->pts[(i+1)%face->numpoints], face);    
  459. }
  460.  
  461. /*
  462. =============
  463. CheckVertexes
  464. /* debugging 
  465. =============
  466. */
  467. void CheckVertexes (void)
  468. {
  469.     int        cb, c0, c1, c2, c3;    
  470.     hashvert_t    *hv;
  471.     
  472.     cb = c0 = c1 = c2 = c3 = 0;
  473.     for (hv=hvertex ; hv!=hvert_p ; hv++)
  474.     {
  475.         if (hv->numedges < 0 || hv->numedges & 1)
  476.             cb++;
  477.         else if (!hv->numedges)
  478.             c0++;
  479.         else if (hv->numedges == 2)
  480.             c1++;
  481.         else if (hv->numedges == 4)
  482.             c2++;
  483.         else
  484.             c3++;
  485.     }
  486.     
  487.     ShowTempEntry("%5i bad edge points", cb);
  488.     ShowTempEntry ("%5i 0 edge points", c0);
  489.     ShowTempEntry ("%5i 2 edge points", c1);
  490.     ShowTempEntry ("%5i 4 edge points", c2);
  491.     ShowTempEntry ("%5i 6+ edge points", c3);
  492. }
  493.  
  494. /*
  495. =============
  496. CheckEdges
  497. /* debugging 
  498. =============
  499. */
  500. void CheckEdges (void)
  501. {
  502.     dedge_t    *edge;
  503.     int        i;
  504.     dvertex_t    *d1, *d2;
  505.     face_t        *f1, *f2;
  506.     int        c_nonconvex;
  507.     int        c_multitexture;
  508.     
  509.     c_nonconvex = c_multitexture = 0;
  510.     
  511. /*    CheckVertexes (); */
  512.     
  513.     for (i=1 ; i < numedges ; i++)
  514.     {
  515.         edge = &dedges[i];
  516.         if (!edgefaces[i][1])
  517.         {
  518.             d1 = &dvertexes[edge->v[0]];
  519.             d2 = &dvertexes[edge->v[1]];
  520.             ShowWarningEntry("Unshared edge:");
  521.             ShowWarningEntry("(%.2f, %.2f, %.2f) (%.2f, %.2f, %.2f)",
  522.                 d1->point[0], d1->point[1], d1->point[2],
  523.                 d2->point[0], d2->point[1], d2->point[2]);
  524.             sleep(1);
  525.                 }
  526.         else
  527.         {
  528.             f1 = edgefaces[i][0];
  529.             f2 = edgefaces[i][1];
  530.             if (f1->planeside != f2->planeside)
  531.                 continue;
  532.             if (f1->planenum != f2->planenum)
  533.                 continue;
  534.                 
  535.             /* on the same plane, might be discardable */
  536.             if (f1->texturenum == f2->texturenum)
  537.             {
  538.                 hvertex[edge->v[0]].numedges-=2;
  539.                 hvertex[edge->v[1]].numedges-=2;
  540.                 c_nonconvex++;
  541.             }
  542.             else
  543.                 c_multitexture++;
  544.         }
  545.     }
  546.  
  547. /*    qprintf ("%5i edges\n", i); */
  548. /*    qprintf ("%5i c_nonconvex\n", c_nonconvex); */
  549. /*    qprintf ("%5i c_multitexture\n", c_multitexture); */
  550.  
  551. /*    CheckVertexes (); */
  552. }
  553.  
  554.  
  555. /*
  556. ================
  557. MakeFaceEdges_r
  558. ================
  559. */
  560. void MakeFaceEdges_r (node_t *node)
  561. {
  562.     face_t    *f;
  563.     
  564.     if (node->planenum == PLANENUM_LEAF)
  565.         return;
  566.         
  567.     for (f=node->faces ; f ; f=f->next)
  568.         FindFaceEdges (f);
  569.         
  570.     MakeFaceEdges_r (node->children[0]);
  571.     MakeFaceEdges_r (node->children[1]);
  572.  
  573.     PercentBar(++FaceEdgeCur * 256 / FaceEdgesTotal);
  574. }
  575.  
  576. /*
  577. ================
  578. MakeFaceEdges
  579. ================
  580. */
  581. void MakeFaceEdges (node_t *headnode, int count)
  582. {
  583.     ShowStatusEntry("Making face edges.  (%d total)", count);
  584.         
  585.     FaceEdgesTotal = count;
  586.     FaceEdgeCur = 0;
  587.     PercentBar(0);
  588.  
  589.         InitHash ();
  590.     c_tryedges = 0;
  591.     c_cornerverts = 0;
  592.  
  593.     MakeFaceEdges_r (headnode);
  594.  
  595. /*    CheckEdges (); */
  596.  
  597.         GrowNodeRegions (headnode);
  598.  
  599.     firstmodeledge = numedges;
  600.     firstmodelface = numfaces;
  601.  
  602.     PercentBar(0);
  603. }
  604.  
  605.